package com.leetcode.partition2;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/26 9:21
 */
public class LC115不同的子序列 {

    public static int numDistinct(String s, String t) {
        return dynamicProgramming(s.toCharArray(), t.toCharArray());
    }

    public static void main(String[] args) {
        System.out.println(numDistinct("baegg", "bag"));
    }

    /**
     * 状态转移方程式：dp[i][j]代表字符串s在[0, i-1]和字符串t在[0, j-1]内，t在s中出现的个数 当s[i-1]==t[j-1]时，dp[i][j]可以由两部分组成，
     * 一部分是用s[i-1]来匹配，个数为dp[i-1][j-1]，另一部分是不用s[i-1]来匹配，个数为dp[i-1][j]；dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。
     * 当s[i-1]!=t[j-1]时，dp[i][j]只有一部分，即是不用s[i-1]来匹配，dp[i][j]=dp[i-1][j].
     * 初始化：dp[i][0]表示空字符串在字符串s[0, i-1]中空格串出现的个数，即当s[0, i-1]全部删除完才能和空格串匹配，dp[i][0]=1；而dp[0][j]表示
     * t[j-1]在空格串中出现的个数，很显然，无论如何空格串都不能通过删除字符串来匹配t[j-1]，因此dp[0][j]=0
     */
    private static int dynamicProgramming(final char[] array1, final char[] array2) {
        int[][] dp = new int[array1.length + 1][array2.length + 1];
        //初始化
        Arrays.fill(dp[0], 0);
        for (int i = 0; i < dp.length; i++) dp[i][0] = 1;

        for (int i = 1; i <= array1.length; i++) {
            for (int j = 1; j <= array2.length; j++) {
                if (array1[i - 1] == array2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    continue;
                }
                dp[i][j] = dp[i - 1][j];
            }
        }
        Arrays.stream(dp).forEach(item -> System.out.println(Arrays.toString(item)));
        return dp[array1.length][array2.length];
    }
}
